package com.fengye.algorithms.leecode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author fengye
 * @Date 2023/4/8 11:08
 **/
public class StringMinWindow76 {
    public String minWindow(String s, String t) {
        int tl = t.length();
        int sl = s.length();
        if(sl < tl) {
            return "";
        }

        Map<Character, Integer> tMap = new HashMap<>();
        for(int i=0; i < tl;i++) {
            tMap.put(t.charAt(i), tMap.getOrDefault(t.charAt(i), 0) + 1);
        }

        int left = 0;
        int right = 0;
        int start = -1;
        int end = -1;
        int min = Integer.MAX_VALUE;
        Map<Character, Integer> subMap = new HashMap<>();
        while(right < sl) {
            char sr = s.charAt(right);
            if(right < sl && tMap.containsKey(sr)) {
                subMap.put(sr, subMap.getOrDefault(sr, 0) + 1);
            }

            while (checkContainsKey(tMap, subMap) && left <= right) {
                int temp = right -left + 1;
                if(temp < min) {
                    min = temp;
                    start = left;
                    end = start + min;
                }
                char slc = s.charAt(left);
                if(subMap.containsKey(slc)) {
                    subMap.put(slc, subMap.getOrDefault(slc, 0) - 1);
                }
                left ++;
            }

            right++;

        }
        return start == -1 ? "" : s.substring(start, end);
    }

    public boolean checkContainsKey(Map<Character, Integer> tMap, Map<Character, Integer> subMap) {
        for(Map.Entry<Character, Integer> entry : tMap.entrySet()) {
            if(!subMap.containsKey(entry.getKey())) {
                return false;
            } else {
                if(subMap.get(entry.getKey()) < entry.getValue()) {
                    return false;
                }
            }
        }
        return true;
    }
}
